This application claims the benefit of the Korean Application No. P2000-71956 filed on Nov. 30, 2000, which is hereby incorporated by reference.
1. Field of the Invention
The present invention relates to a data processing system having a plurality of Memory Access Units (MAU), and more particularly, to a system and a method for arbitrating access to a shared memory in a data processing system.
2. Discussion of the Related Art
In general, a data processing system (i.e., a digital video processor), which has a plurality of Memory Access Units (MAU), has an arbiter that allows a MAU to access to a memory data bus each time. FIG. 1 illustrates a typical digital video processor showing interfaces between an arbiter and each MAU. As shown in the figure, the system includes a plurality of MAUs 102-106, an arbiter 101, and a memory 100.
Each MAU initially activates a requesting signal and outputs its priority level set to an initial priority value to the arbiter 101. Then the arbiter 101 performs the arbitration process that allows a selected MAU to access to the memory 100 by sending an acknowledgement signal to the MAU.
The MAUs shown in FIG. 1 are a transport decoder 102, a video decoder 103, a format converter 104, and a host interface 106.
First, the transport decoder 102 initially selects a desired program among many programs included in a channel and separates audio and video bit streams from the data. Thereafter, the separated video and audio bit streams are outputted to the video decoder 103 and the audio decoder 105, respectively, after passing through the arbiter 101 and the memory data bus.
The video decoder 103 eliminates the overhead portion (i.e., header information and starting code) of the video bit streams received and carries out processes including Variable Length Decoding (VLD), inverse quantization, Inverse Discrete Cosine Decoding (IDCT), and motion compensation using motion vectors. Then the data processed in the video decoder 103 get stored in the memory 100 after passing through the arbiter 101 and the memory data bus.
The format converter 104 reads the data stored in the memory 100 and converts their display format. Then the format-converted data are stored again in the memory via the arbiter 101 and the memory data bus.
The audio decoder 105 compensates the audio bit streams, which are inputted using an MPEG or Audio Coding-3 (AC-3) algorithm, and stores the compensated data in the memory 100.
The arbiter 101 controls the data inputs/outputs to the memory 100 and the memory data bus. In other words, it controls the data flows between the memory 100 and each MAU. If the arbiter 101 selects the video decoder 103 as a result of its arbitration process, the arbiter 101 sends an acknowledgement signal to the video decoder 103 so that it can access to the memory 100.
When selecting an arbitration algorithm for an arbiter, the fairness and efficiency factors must be considered based on the characteristics and structure of the data processing system. An example of the algorithm, to which the fairness factor is applied, is the algorithm having the Round Robin structure. Using the Round Robin structure, all the MAUs can access to the memory in a predetermined order regardless of their priority values. Once a MAU accesses to the memory, it has to wait until all other MAUs participating in the arbitration access to the memory in order to re-access to the memory. Therefore, the arbitration algorithm having the Round Robin structure gives an equitable chance to each of the MAUs that have requested for accessing to the memory.
However, this type of algorithm is not suitable for a digital video processor, in which the MAUs having higher priority values need to access to memory more frequently than others with limited time. Therefore, an arbitration algorithm implementing a priority structure is often used.
The algorithm having the priority structure still has few disadvantages. The MAUs having relatively lower priority values may not be able to access to the memory for a long time while other MAUs use the memory data bus exclusively. This is called as starvation. The occurrence of such starvation may result an abnormal behavior of the system.
Accordingly, the present invention is directed to a method and system for arbitrating access to a shared memory in a data processing system having a plurality of data access units that substantially obviates one or more problems due to limitations and disadvantages of the related art.
An object of the present invention is to provide a method and system for arbitrating access to a memory in a data processing system having an arbiter that efficiently allows each memory access unit to access to the memory.
Another object of the present invention is to provide a method and system for arbitrating access to a memory in a data processing system including memory access units, each unit being able to reset its priority level to a top priority value if necessary.
Another object of the present invention is to provide a method and system for arbitrating access to a memory in a data processing system having an arbiter being able to give a top priority to each MAU that have failed to access to the memory for a predetermined starvation period.
Additional advantages, objects, and features of the invention will be set forth in part in the description which follows and in part will become apparent to those having ordinary skill in the art upon examination of the following or may be learned from practice of the invention. The objectives and other advantages of the invention may be realized and attained by the structure particularly pointed out in the written description and claims hereof as well as the appended drawings.
To achieve these objects and other advantages and in accordance with the purpose of the invention, as embodied and broadly described herein, a memory accessing method for a memory access unit (MAU) in a data processing system having a memory includes the steps of (a) sending an access requesting signal and a first priority signal to an arbiter, said first priority signal indicating a priority level initially set to an initial priority value; (b) resetting said priority level to a top priority value and sending a second priority signal indicating said reset priority level to said arbiter; and (c) receiving an acknowledgement signal from said arbiter and accessing to said memory.
In another aspect of the present invention, a memory accessing method for a MAU in a data processing system having a memory includes the steps of (a) sending an access requesting signal and a first priority signal to an arbiter, said first priority signal indicating a priority level initially set to an initial priority value; and (b) determining whether to reset said priority level to a top priority value.
The method further includes (c) resetting said priority level to said top priority value and sending a second priority signal indicating said reset priority level to said arbiter if it is determined to reset said initially set priority level in the step (b); and (d) receiving an acknowledgement signal from said arbiter and accessing to said memory.
In another aspect of the present invention, a method of arbitrating access to a memory for an arbiter in a data processing system having MAUs includes the steps of (a) receiving an access requesting signal and a first priority signal from each of an original set of MAUs, said first priority signal indicating a priority level initially set to an initial priority value for each MAU; and (b) identifying a first set of top priority MAUs whose priority levels are set to a top priority value.
The method further includes the steps of (c) selecting a first final MAU among said first set of top priority MAUs; and (d) sending an acknowledgement signal to said first final MAU.
The method further includes the steps of (e) identifying a second set of top priority MAUs if none of said first set of top priority MAUs are identified in the step (b), each of said second set of top priority MAUs being unable to access to said memory for a predetermined starvation period; (f) selecting a second final MAU among said second set of top priority MAUs; and (g) sending said acknowledgement signal to said second final MAU.
In addition, the method further includes the steps of (h) selecting a third final MAU among said original set of MAUs if none of said second set of top priority MAUs are identified in the step (e); and (i) sending said acknowledgement signal to said third final MAU.
In another aspect of the present invention, a system for accessing to a memory in a data processing system includes a plurality of memory access units (MAU), each MAU initially sending an access requesting signal and a first priority signal that indicates a priority level set to an initial priority value, each MAU resetting said initially set priority level to a top priority value if necessary and sending a second priority signal indicating said reset priority level; and an arbiter identifying a first set of top priority MAUs whose priority levels are reset to said top priority value, said arbiter subsequently selecting a first final MAU among said first set of top priority MAUs and sending an acknowledgement signal to said first final MAU.
The arbiter included in the system further identifies a second set of top priority MAUs being unable to access to said memory for a predetermined starvation period if none of said first set of top priority MAUs are identified, said arbiter selecting a second final MAU among said second set of top priority MAUs and sending said acknowledgement signal to said second final MAU.
In addition, the arbiter further selects a third final MAU among said plurality of MAUs if non of said second set of top priority MAUs are identified and sends said acknowledgement signal to said third final MAU.
It is to be understood that both the foregoing general description and the following detailed description of the present invention are exemplary and explanatory and are intended to provide further explanation of the invention as claimed.